COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a01.tex[154,phy] \today\hfill}

\bigskip
\noindent
{\bf Not All Languages are FMLs}

There are languages for which no finite machine is a recognizer. There are
several proofs. The first is called a diagonal proof, after the style
of the following classical proof that there are irrational numbers.

Imagine writing in a column all the rational numbers between 0 and~1 in
a systematic order, with their decimal expansions beside them.
$$\baselineskip 18pt\vcenter{\halign{$#$\hfil\qquad&$#$\hfil\cr
1/2&0.\;5\;0\;0\;0\;0\;0\;0\cr
1/3&0.\;3\;3\;3\;3\;3\;3\;3\cr
2/3&0.\;6\;6\;6\;6\;6\;6\;6\cr
1/4&0.\;2\;5\;0\;0\;0\;0\;0\cr
2/4&0.\;5\;0\;0\;0\;0\;0\;0\cr
3/4&0.\;7\;5\;0\;0\;0\;0\;0\cr
1/5&0.\;2\;0\;0\;0\;0\;0\;0\cr
2/5&0.\;4\;0\;0\;0\;0\;0\;0\;0\cr
3/5&0.\;6\;0\;0\;0\;0\;0\;0\;0\;0\cr
4/5&0.\;8\;0\;0\;0\;0\;0\;0\;0\;0\;0\cr
1/6&0.\;1\;6\;6\;6\;6\;6\;6\;6\;6\;6\;6\;\ldots\cr
2/6&0.\;3\;3\;3\;3\;3\;3\;3\;3\;3\;3\;3\;3\;\ldots\cr
3/6&0.\;5\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\cr}}$$
Reading down the circled digits on the diagonal, we find another number,
$0.5360000000630\ldots\,$. Change all of its digits to~0, except that
zeroes are changed to ones; it becomes $0.0001111111001\ldots\,$.
This number is different in at least one digit from any rational number;
for example, it is different from $3/5$ in the ninth decimal place
because of the way it was constructed. In fact, the diagonal proof
shows that any (infinite) set of numbers that can be set in a numbered
column omits some number.

The analogous proof about languages shows that no technique for naming
a class of languages includes all languages, or even all languages
in $\{0,1\}↑{\ast}$. Write down in a column all the names of languages,
and in a second column encode these names in binary:
$$\vcenter{\halign{$#$\hfil\qquad&#\hfil\cr
\emptyset&110\cr
\epsilon&111\cr
0&000\cr
1&010\cr
0↑{\ast}∪1&000 011 010 001\cr
(0∪11)↑{\ast}1&100 000 010 001 001 101 011 001\cr
(0∪1)↑{\ast}&100 000 010 001 101 011\cr
\quad\vdots\cr}}$$
$$\vcenter{\halign{#\hfil\quad&$#$\hfil\qquad&#\hfil\cr
code:&0&000\cr
&1&001\cr
&∪&010\cr
&\ast&011\cr
&(&100\cr
&)&101\cr
&\emptyset&110\cr
&\epsilon&111\cr}}$$
Notice that the code for language $(0∪1)↑{\ast}$ belongs to that language;
none of the other codes happen to belong to the language they name.
{\bf Drill:} What about the codes for $(0∪1)↑{\ast}1$, \dots ?
Now let language~$L$ consist of those codes for regular expressions that
don't belong to the languages they name. For example, $L$~includes 000
but not 100 000 010 001 101 011.
We will prove $L$~is not a~FML. If $L$~were, it would have a regular
expression~$e$, and $e$~would have a code~$c$ naming~$L$. Two possibilities
arise:

\disleft 25pt:
(1):$c\in L$. Then $c$ belongs to the language it names, and by definition
of~$L$, $c\notin L$, contradiction.

\disleft 25pt:
(2):$c\notin L$. Then $c$ does not belong to the language it names, and by
definition of~$L$, $c\in L$, contradiction.

\noindent
So, assuming $L$ to be a FML leads to contradiction; no finite machine
recognizes~$L$. We shall later have the tools to show that some non-finite
machines can recognize~$L$.

A second proof that there are languages that are not FMLs is simpler, but
does not generalize to so many other kinds of languages. Let
$L=\{0↑i1↑i,i≥0\}$; that is, $L=\{\epsilon,01,0011,000111,\hbox{ etc.}\}$.
Suppose there were a DFM for~$L$. Let it read zeroes until it goes through
some state~$q$ twice, say after reading~$j$ zeroes and after $k$~zeroes,
$0≤j<k$. Now start the machine again letting it read $j$~zeroes to reach
state~$q$, and then $j$~ones to reach state $q'\in F$. Start it one more
time, letting it read $k$~zeroes to reach~$q$, and $j$~ones to reach
$q'\in F$. So it accepts $0↑k1↑j$, contrary to the definition of~$L$.
The key fact about the machine we used is that, being finite, it must
repeat a state. This proof is a particular application of the {\sl pumping
theorem\/}, soon to be shown, the most powerful tool for showing particular
languages are not FMLs.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd
First draft (not published)
April 22 1986.
%revised date;
%subsequently revised.

\bye